from collections import deque
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
def bfs(s):
q = deque()
q.append(s)
dist = [inf] * (n + 1)
dist[s] = 0
while q:
i = q.popleft()
di = dist[i]
for j in G[i]:
if dist[j] == inf:
dist[j] = di + 1
q.append(j)
return dist
n = int(input())
inf = pow(10, 9) + 1
G = [[] for _ in range(n + 1)]
for i in range(1, n + 1):
g = list(input().rstrip())
for j in range(n):
if g[j] & 1:
G[i].append(j + 1)
dist = [bfs(i) for i in range(n + 1)]
m = int(input())
p = list(map(int, input().split()))
dp = [inf] * m
dp[0] = 0
parent = [-1] * m
for i in range(m):
di = dist[p[i]]
dpi = dp[i]
for j in range(i + 1, min(i + n, m)):
if di[p[j]] ^ (j - i):
continue
if dp[j] > dpi + 1:
dp[j] = dpi + 1
parent[j] = i
k = dp[-1] + 1
i = m - 1
v = []
while i:
v.append(p[i])
i = parent[i]
v.append(p[0])
v.reverse()
print(k)
sys.stdout.write(" ".join(map(str, v)))#include<bits/stdc++.h>
using namespace std;
const int N=1e2+7;
const int INF=0x3f3f3f3f;
int n,m;
int dis[N][N];
char s[N];
vector<int>ans;
int lst[N];
int p[1000007],dp[1000007];
signed main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>s;
for(int j=0;j<n;j++){
if(s[j]=='1')dis[i][j+1]=1;
else dis[i][j+1]=INF;
}
}
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
}
}
}
cin>>m;
for(int i=1;i<=m;i++)cin>>p[i];
for(int i=0;i<=m;i++)dp[i]=INF;
dp[1]=1;lst[p[1]]=1;
for(int i=2;i<=m;i++){
for(int j=1;j<=n;j++){
if(j==p[i])continue;
//cout<<lst[j]<<" "<<dis[j][p[i]]<<"\n";
if(lst[j]&&dis[j][p[i]]==i-lst[j]){
dp[i]=min(dp[i],dp[lst[j]]+1);}
}
lst[p[i]]=i;
}
int lst=m;
ans.push_back(p[m]);
for(int i=m-1;i>=1;i--){
if(dis[p[i]][p[lst]]==lst-i&&dp[i]==dp[lst]-1){
ans.push_back(p[i]);
lst=i;
}
}
reverse(ans.begin(),ans.end());
cout<<ans.size()<<"\n";
for(auto v:ans)cout<<v<<" ";
return 0;
}
1302. Deepest Leaves Sum | 1209. Remove All Adjacent Duplicates in String II |
994. Rotting Oranges | 983. Minimum Cost For Tickets |
973. K Closest Points to Origin | 969. Pancake Sorting |
967. Numbers With Same Consecutive Differences | 957. Prison Cells After N Days |
946. Validate Stack Sequences | 921. Minimum Add to Make Parentheses Valid |
881. Boats to Save People | 497. Random Point in Non-overlapping Rectangles |
528. Random Pick with Weight | 470. Implement Rand10() Using Rand7() |
866. Prime Palindrome | 1516A - Tit for Tat |
622. Design Circular Queue | 814. Binary Tree Pruning |
791. Custom Sort String | 787. Cheapest Flights Within K Stops |
779. K-th Symbol in Grammar | 701. Insert into a Binary Search Tree |
429. N-ary Tree Level Order Traversal | 739. Daily Temperatures |
647. Palindromic Substrings | 583. Delete Operation for Two Strings |
518. Coin Change 2 | 516. Longest Palindromic Subsequence |
468. Validate IP Address | 450. Delete Node in a BST |